use std::ffi::c_void;
#[repr(C)]
struct ArrayList {
    data: *mut *mut c_void,
    length: u32,
    _alloced: u32,
}
type ArrayListValue = *mut c_void;
type ArrayListEqualFunc = Option<extern "C" fn(ArrayListValue, ArrayListValue) -> i32>;
type ArrayListCompareFunc = Option<extern "C" fn(ArrayListValue, ArrayListValue) -> i32>;
fn arraylist_new(mut length: u32) -> *mut ArrayList {
    if length == 0 {
        length = 16;
    }
    let new_arraylist = unsafe { malloc(mem::size_of::<ArrayList>()) } as *mut ArrayList;
    if new_arraylist.is_null() {
        return std::ptr::null_mut();
    }
    unsafe {
        (*new_arraylist)._alloced = length;
        (*new_arraylist).length = 0;
    }
    let data = unsafe { malloc((length as usize) * mem::size_of::<ArrayListValue>()) }
        as *mut ArrayListValue;
    if data.is_null() {
        unsafe {
            free(new_arraylist as *mut c_void);
        }
        return std::ptr::null_mut();
    }
    unsafe {
        (*new_arraylist).data = data;
    }
    new_arraylist
}
fn arraylist_free(arraylist: *mut ArrayList) {
    if !arraylist.is_null() {
        unsafe {
            libc::free((*arraylist).data as *mut libc::c_void);
            libc::free(arraylist as *mut libc::c_void);
        }
    }
}
fn arraylist_enlarge(arraylist: *mut ArrayList) -> i32 {
    unsafe {
        let newsize = (*arraylist)._alloced * 2;
        let data = libc::realloc(
            (*arraylist).data as *mut libc::c_void,
            (std::mem::size_of::<ArrayListValue>() as usize) * newsize as usize,
        ) as *mut ArrayListValue;
        if data.is_null() {
            0
        } else {
            (*arraylist).data = data;
            (*arraylist)._alloced = newsize;
            1
        }
    }
}
fn arraylist_insert(arraylist: *mut ArrayList, index: u32, data: ArrayListValue) -> i32 {
    unsafe {
        if index > (*arraylist).length {
            return 0;
        }
        if (*arraylist).length + 1 > (*arraylist)._alloced {
            if arraylist_enlarge(arraylist) == 0 {
                return 0;
            }
        }
        let elements_to_move = (*arraylist).length - index;
        if elements_to_move > 0 {
            let src = (*arraylist).data.add(index as usize);
            let dest = src.add(1);
            let byte_count = (elements_to_move as usize) * std::mem::size_of::<*mut c_void>();
            libc::memmove(dest as *mut _, src as *const _, byte_count);
        }
        *(*arraylist).data.add(index as usize) = data;
        (*arraylist).length += 1;
        1
    }
}
fn arraylist_append(arraylist: *mut ArrayList, data: ArrayListValue) -> i32 {
    unsafe { arraylist_insert(arraylist, (*arraylist).length, data) }
}
fn arraylist_prepend(arraylist: *mut ArrayList, data: ArrayListValue) -> i32 {
    unsafe { arraylist_insert(arraylist, 0, data) }
}
fn arraylist_remove_range(arraylist: *mut ArrayList, index: u32, length: u32) {
    unsafe {
        if (*arraylist).length < index || (*arraylist).length - index < length {
            return;
        }
        let src = (*arraylist).data.add((index + length) as usize);
        let dst = (*arraylist).data.add(index as usize);
        let count = (*arraylist).length - (index + length);
        std::ptr::copy(src, dst, count as usize);
        (*arraylist).length -= length;
    }
}
fn arraylist_remove(arraylist: *mut ArrayList, index: u32) {
    arraylist_remove_range(arraylist, index, 1);
}
fn arraylist_index_of(
    arraylist: *mut ArrayList,
    callback: ArrayListEqualFunc,
    data: ArrayListValue,
) -> i32 {
    unsafe {
        let arraylist_ref = &*arraylist;
        for i in 0..arraylist_ref.length {
            let element = *arraylist_ref.data.offset(i as isize);
            if let Some(cb) = callback {
                if cb(element, data) != 0 {
                    return i as i32;
                }
            }
        }
    }
    -1
}
fn arraylist_clear(arraylist: *mut ArrayList) {
    unsafe {
        (*arraylist).length = 0;
    }
}
fn arraylist_sort_internal(
    list_data: *mut ArrayListValue,
    list_length: u32,
    compare_func: ArrayListCompareFunc,
) {
    if list_length <= 1 {
        return;
    }
    unsafe {
        let pivot = *list_data.offset((list_length - 1) as isize);
        let mut list1_length = 0;
        for i in 0..(list_length - 1) {
            let current = *list_data.offset(i as isize);
            let cmp = (compare_func.unwrap())(current, pivot);
            if cmp < 0 {
                let tmp = *list_data.offset(i as isize);
                *list_data.offset(i as isize) = *list_data.offset(list1_length as isize);
                *list_data.offset(list1_length as isize) = tmp;
                list1_length += 1;
            }
        }
        let list2_length = list_length - list1_length - 1;
        *list_data.offset((list_length - 1) as isize) = *list_data.offset(list1_length as isize);
        *list_data.offset(list1_length as isize) = pivot;
        arraylist_sort_internal(list_data, list1_length, compare_func);
        arraylist_sort_internal(
            list_data.offset(list1_length as isize + 1),
            list2_length,
            compare_func,
        );
    }
}
fn arraylist_sort(arraylist: *mut ArrayList, compare_func: ArrayListCompareFunc) {
    unsafe {
        arraylist_sort_internal((*arraylist).data, (*arraylist).length, compare_func);
    }
}
fn main() {}

